Xarxa de flux

En teoria de grafs, una xarxa de flux és un graf dirigit en què cada aresta està ponderada amb un flux i una capacitat. La suma del flux d'una aresta no pot ser superior a la seva capacitat. Moltes vegades s'anomena al graf dirigit, xarxa, als vèrtexs, nodes, i a les arestes, arcs. La suma de flux que entra en un node ha de ser igual a la suma de flux que en surt, a excepció de les fonts, que tenen més flux sortint, o els pous, que tenen més flux entrant. Una xarxa pot ser utilitzada per modelitzar el tràfic en un sistema de carreteres, líquids dins de canonades, corrents en un circuit elèctric, o qualsevol cosa que viatgi a través d'una xarxa de nodes.